//重新排列数组使得数组左边为奇数，右边为偶数
//快速排序的思想，选择一个基准值，将奇偶分为两边即可


#include <iostream>

using namespace std;

int rerange(int arr[] ,int n)
{
    if(arr == NULL || n<=0)
    {
        return 0;
    }
    int base = arr[0]; //基准值
    int i = 0,j = n-1; //左右指针
    //基准值无论是奇数还是偶数，基准值左边都是奇数，右边都是偶数
    while(i<j)
    {
        //从右边找
        while(i<j && arr[j]%2==0)  //找到右边的奇数
        {
            j--;
        }
        arr[i] = arr[j];
        //从左边开始找，找到左边的偶数
        while(i<j && arr[i]%2!=0)
        {
            i++;
        }
        arr[j] = arr[i];
    }
    arr[j] = base;
    return 1;
}

void show(int arr[] ,int n)
{
    for(int i = 0;i<n;i++)
    {
        cout<<arr[i]<<",";
    }
}
int main()
{
    int arr[] = {1,2,3,4,5,6,7,8,9};
    rerange(arr,9);
    show(arr,9);
    cout<<endl;
    system("pause");
    return 0;
}
